home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / samba.idb / usr / samba / src / source / ubiqx / ubi_AVLtree.c.z / ubi_AVLtree.c
Encoding:
C/C++ Source or Header  |  1998-10-28  |  28.5 KB  |  696 lines
  1. /* ========================================================================== **
  2.  *                              ubi_AVLtree.c
  3.  *
  4.  *  Copyright (C) 1991-1997 by Christopher R. Hertel
  5.  *
  6.  *  Email: crh@ubiqx.mn.org
  7.  * -------------------------------------------------------------------------- **
  8.  *
  9.  *  This module provides an implementation of AVL height balanced binary
  10.  *  trees.  (Adelson-Velskii, Landis 1962)
  11.  *
  12.  *  This file implements the core of the height-balanced (AVL) tree management
  13.  *  routines.  The header file, ubi_AVLtree.h, contains function prototypes
  14.  *  for all "exported" functions.
  15.  *
  16.  * -------------------------------------------------------------------------- **
  17.  *
  18.  *  This library is free software; you can redistribute it and/or
  19.  *  modify it under the terms of the GNU Library General Public
  20.  *  License as published by the Free Software Foundation; either
  21.  *  version 2 of the License, or (at your option) any later version.
  22.  *
  23.  *  This library is distributed in the hope that it will be useful,
  24.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26.  *  Library General Public License for more details.
  27.  *
  28.  *  You should have received a copy of the GNU Library General Public
  29.  *  License along with this library; if not, write to the Free
  30.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  31.  *
  32.  * -------------------------------------------------------------------------- **
  33.  *
  34.  * Log: ubi_AVLtree.c,v
  35.  * Revision 2.5  1997/12/23 04:00:42  crh
  36.  * In this version, all constants & macros defined in the header file have
  37.  * the ubi_tr prefix.  Also cleaned up anything that gcc complained about
  38.  * when run with '-pedantic -fsyntax-only -Wall'.
  39.  *
  40.  * Revision 2.4  1997/07/26 04:36:20  crh
  41.  * Andrew Leppard, aka "Grazgur", discovered that I still had my brains tied
  42.  * on backwards with respect to node deletion.  I did some more digging and
  43.  * discovered that I was not changing the balance values correctly in the
  44.  * single rotation functions.  Double rotation was working correctly because
  45.  * the formula for changing the balance values is the same for insertion or
  46.  * deletion.  Not so for single rotation.
  47.  *
  48.  * I have tested the fix by loading the tree with over 44 thousand names,
  49.  * deleting 2,629 of them (all those in which the second character is 'u')
  50.  * and then walking the tree recursively to verify that the balance factor of
  51.  * each node is correct.  Passed.
  52.  *
  53.  * Thanks Andrew!
  54.  *
  55.  * Also:
  56.  * + Changed ubi_TRUE and ubi_FALSE to ubi_trTRUE and ubi_trFALSE.
  57.  * + Rewrote the ubi_tr<func> macros because they weren't doing what I'd
  58.  *   hoped they would do (see the bottom of the header file).  They work now.
  59.  *
  60.  * Revision 2.3  1997/06/03 04:41:35  crh
  61.  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid causing
  62.  * problems.
  63.  *
  64.  * Revision 2.2  1995/10/03 22:16:01  CRH
  65.  * Ubisized!
  66.  *
  67.  * Revision 2.1  95/03/09  23:45:59  CRH
  68.  * Added the ModuleID static string and function.  These modules are now
  69.  * self-identifying.
  70.  * 
  71.  * Revision 2.0  95/03/05  14:10:51  CRH
  72.  * This revision of ubi_AVLtree coincides with revision 2.0 of ubi_BinTree,
  73.  * and so includes all of the changes to that module.  In addition, a bug in
  74.  * the node deletion process has been fixed.
  75.  *
  76.  * After rewriting the Locate() function in ubi_BinTree, I decided that it was
  77.  * time to overhaul this module.  In the process, I discovered a bug related
  78.  * to node deletion.  To fix the bug, I wrote function Debalance().  A quick
  79.  * glance will show that it is very similar to the Rebalance() function.  In
  80.  * previous versions of this module, I tried to include the functionality of
  81.  * Debalance() within Rebalance(), with poor results.
  82.  *
  83.  * Revision 1.0  93/10/15  22:58:56  CRH
  84.  * With this revision, I have added a set of #define's that provide a single,
  85.  * standard API to all existing tree modules.  Until now, each of the three
  86.  * existing modules had a different function and typedef prefix, as follows:
  87.  *
  88.  *       Module        Prefix
  89.  *     ubi_BinTree     ubi_bt
  90.  *     ubi_AVLtree     ubi_avl
  91.  *     ubi_SplayTree   ubi_spt
  92.  *
  93.  * To further complicate matters, only those portions of the base module
  94.  * (ubi_BinTree) that were superceeded in the new module had the new names.
  95.  * For example, if you were using ubi_AVLtree, the AVL node structure was
  96.  * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
  97.  * SplayTree, the locate function was called "ubi_sptLocate", but the next
  98.  * and previous functions remained "ubi_btNext" and "ubi_btPrev".
  99.  *
  100.  * This was not too terrible if you were familiar with the modules and knew
  101.  * exactly which tree model you wanted to use.  If you wanted to be able to
  102.  * change modules (for speed comparisons, etc), things could get messy very
  103.  * quickly.
  104.  *
  105.  * So, I have added a set of defined names that get redefined in any of the
  106.  * descendant modules.  To use this standardized interface in your code,
  107.  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
  108.  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
  109.  * datatype names for the module that you are using.  Just remember to
  110.  * include the header for that module in your program file.  Because these
  111.  * names are handled by the preprocessor, there is no added run-time
  112.  * overhead.
  113.  *
  114.  * Note that the original names do still exist, and can be used if you wish
  115.  * to write code directly to a specific module.  This should probably only be
  116.  * done if you are planning to implement a new descendant type, such as
  117.  * red/black trees.  CRH
  118.  *
  119.  *  V0.0 - May, 1990   -  Written by Christopher R. Hertel (CRH).
  120.  *
  121.  *  ========================================================================= **
  122.  */
  123.  
  124. #include "ubi_AVLtree.h"            /* Header for THIS module.             */
  125. #include <stdlib.h>                 /* Standard C definitions, etc.        */
  126.  
  127. /* ========================================================================== **
  128.  * Static data.
  129.  */
  130.  
  131. static char ModuleID[] = "ubi_AVLtree\n\
  132. \tRevision: 2.5\n\
  133. \tDate: 1997/12/23 04:00:42\n\
  134. \tAuthor: crh\n";
  135.  
  136. /* ========================================================================== **
  137.  * The next set of functions are the AVL balancing routines.  There are left
  138.  * and right, single and double rotations.  The rotation routines handle the
  139.  * rotations and reconnect all tree pointers that might get confused by the
  140.  * rotations.  A pointer to the new subtree root node is returned.
  141.  *
  142.  * Note that L1 and R1 are identical, except that all the RIGHTs and LEFTs
  143.  * are reversed.  The same is true for L2 and R2.  I'm sure that there is
  144.  * a clever way to reduce the amount of code by combining these functions,
  145.  * but it might involve additional overhead, and it would probably be a pain
  146.  * to read, debug, etc.
  147.  * -------------------------------------------------------------------------- **
  148.  */
  149.  
  150. static ubi_avlNodePtr L1( ubi_avlNodePtr p )
  151.   /* ------------------------------------------------------------------------ **
  152.    * Single rotate left.
  153.    *
  154.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  155.    *  Output: A pointer to the new root of the same subtree (now that node
  156.    *          p has been moved).
  157.    * ------------------------------------------------------------------------ **
  158.    */
  159.   {
  160.   ubi_avlNodePtr tmp;
  161.  
  162.   tmp                      = p->Link[ubi_trRIGHT];
  163.   p->Link[ubi_trRIGHT]     = tmp->Link[ubi_trLEFT];
  164.   tmp->Link[ubi_trLEFT]    = p;
  165.  
  166.   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
  167.   tmp->gender              = p->gender;
  168.   if(tmp->Link[ubi_trPARENT])
  169.     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
  170.   p->Link[ubi_trPARENT]    = tmp;
  171.   p->gender                = ubi_trLEFT;
  172.   if( p->Link[ubi_trRIGHT] )
  173.     {
  174.     p->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = p;
  175.     (p->Link[ubi_trRIGHT])->gender           = ubi_trRIGHT;
  176.     }
  177.   p->balance -= ubi_trNormalize( tmp->balance );
  178.   (tmp->balance)--;
  179.   return( tmp );
  180.   } /* L1 */
  181.  
  182. static ubi_avlNodePtr R1( ubi_avlNodePtr p )
  183.   /* ------------------------------------------------------------------------ **
  184.    * Single rotate right.
  185.    *
  186.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  187.    *  Output: A pointer to the new root of the same subtree (now that node
  188.    *          p has been moved).
  189.    * ------------------------------------------------------------------------ **
  190.    */
  191.   {
  192.   ubi_avlNodePtr tmp;
  193.  
  194.   tmp                      = p->Link[ubi_trLEFT];
  195.   p->Link[ubi_trLEFT]      = tmp->Link[ubi_trRIGHT];
  196.   tmp->Link[ubi_trRIGHT]   = p;
  197.  
  198.   tmp->Link[ubi_trPARENT]  = p->Link[ubi_trPARENT];
  199.   tmp->gender              = p->gender;
  200.   if(tmp->Link[ubi_trPARENT])
  201.     (tmp->Link[ubi_trPARENT])->Link[(int)(tmp->gender)] = tmp;
  202.   p->Link[ubi_trPARENT]    = tmp;
  203.   p->gender                = ubi_trRIGHT;
  204.   if(p->Link[ubi_trLEFT])
  205.     {
  206.     p->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = p;
  207.     p->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
  208.     }
  209.   p->balance -= ubi_trNormalize( tmp->balance );
  210.   (tmp->balance)++;
  211.   return( tmp );
  212.   } /* R1 */
  213.  
  214. static ubi_avlNodePtr L2( ubi_avlNodePtr tree )
  215.   /* ------------------------------------------------------------------------ **
  216.    * Double rotate left.
  217.    *
  218.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  219.    *  Output: A pointer to the new root of the same subtree (now that node
  220.    *          p has been moved).
  221.    * ------------------------------------------------------------------------ **
  222.    */
  223.   {
  224.   ubi_avlNodePtr tmp, newroot;
  225.  
  226.   tmp                         = tree->Link[ubi_trRIGHT];
  227.   newroot                     = tmp->Link[ubi_trLEFT];
  228.   tmp->Link[ubi_trLEFT]       = newroot->Link[ubi_trRIGHT];
  229.   newroot->Link[ubi_trRIGHT]  = tmp;
  230.   tree->Link[ubi_trRIGHT]     = newroot->Link[ubi_trLEFT];
  231.   newroot->Link[ubi_trLEFT]   = tree;
  232.  
  233.   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
  234.   newroot->gender             = tree->gender;
  235.   tree->Link[ubi_trPARENT]    = newroot;
  236.   tree->gender                = ubi_trLEFT;
  237.   tmp->Link[ubi_trPARENT]     = newroot;
  238.   tmp->gender                 = ubi_trRIGHT;
  239.  
  240.   if( tree->Link[ubi_trRIGHT] )
  241.     {
  242.     tree->Link[ubi_trRIGHT]->Link[ubi_trPARENT] = tree;
  243.     tree->Link[ubi_trRIGHT]->gender             = ubi_trRIGHT;
  244.     }
  245.   if( tmp->Link[ubi_trLEFT] )
  246.     {
  247.     tmp->Link[ubi_trLEFT]->Link[ubi_trPARENT]   = tmp;
  248.     tmp->Link[ubi_trLEFT]->gender               = ubi_trLEFT;
  249.     }
  250.   if(newroot->Link[ubi_trPARENT])
  251.     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
  252.  
  253.   switch( newroot->balance )
  254.     {
  255.     case ubi_trLEFT :
  256.       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trRIGHT; break;
  257.     case ubi_trEQUAL:
  258.       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
  259.     case ubi_trRIGHT:
  260.       tree->balance = ubi_trLEFT;  tmp->balance = ubi_trEQUAL; break;
  261.     }
  262.   newroot->balance = ubi_trEQUAL;
  263.   return( newroot );
  264.   } /* L2 */
  265.  
  266. static ubi_avlNodePtr R2( ubi_avlNodePtr tree )
  267.   /* ------------------------------------------------------------------------ **
  268.    * Double rotate right.
  269.    *
  270.    *  Input:  p - Pointer to the root of a tree (possibly a subtree).
  271.    *  Output: A pointer to the new root of the same subtree (now that node
  272.    *          p has been moved).
  273.    * ------------------------------------------------------------------------ **
  274.    */
  275.   {
  276.   ubi_avlNodePtr tmp, newroot;
  277.  
  278.   tmp                         = tree->Link[ubi_trLEFT];
  279.   newroot                     = tmp->Link[ubi_trRIGHT];
  280.   tmp->Link[ubi_trRIGHT]      = newroot->Link[ubi_trLEFT];
  281.   newroot->Link[ubi_trLEFT]   = tmp;
  282.   tree->Link[ubi_trLEFT]      = newroot->Link[ubi_trRIGHT];
  283.   newroot->Link[ubi_trRIGHT]  = tree;
  284.  
  285.   newroot->Link[ubi_trPARENT] = tree->Link[ubi_trPARENT];
  286.   newroot->gender             = tree->gender;
  287.   tree->Link[ubi_trPARENT]    = newroot;
  288.   tree->gender                = ubi_trRIGHT;
  289.   tmp->Link[ubi_trPARENT]     = newroot;
  290.   tmp->gender                 = ubi_trLEFT;
  291.  
  292.   if( tree->Link[ubi_trLEFT] )
  293.     {
  294.     tree->Link[ubi_trLEFT]->Link[ubi_trPARENT]  = tree;
  295.     tree->Link[ubi_trLEFT]->gender              = ubi_trLEFT;
  296.     }
  297.   if( tmp->Link[ubi_trRIGHT] )
  298.     {
  299.     tmp->Link[ubi_trRIGHT]->Link[ubi_trPARENT]  = tmp;
  300.     tmp->Link[ubi_trRIGHT]->gender              = ubi_trRIGHT;
  301.     }
  302.   if(newroot->Link[ubi_trPARENT])
  303.     newroot->Link[ubi_trPARENT]->Link[(int)(newroot->gender)] = newroot;
  304.  
  305.   switch( newroot->balance )
  306.     {
  307.     case ubi_trLEFT  :
  308.       tree->balance = ubi_trRIGHT; tmp->balance = ubi_trEQUAL; break;
  309.     case ubi_trEQUAL :
  310.       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trEQUAL; break;
  311.     case ubi_trRIGHT :
  312.       tree->balance = ubi_trEQUAL; tmp->balance = ubi_trLEFT;  break;
  313.     }
  314.   newroot->balance = ubi_trEQUAL;
  315.   return( newroot );
  316.   } /* R2 */
  317.  
  318.  
  319. static ubi_avlNodePtr Adjust( ubi_avlNodePtr p, char LorR )
  320.   /* ------------------------------------------------------------------------ **
  321.    * Adjust the balance value at node *p.  If necessary, rotate the subtree
  322.    * rooted at p.
  323.    *
  324.    *  Input:  p    -  A pointer to the node to be adjusted.  One of the
  325.    *                  subtrees of this node has changed height, so the
  326.    *                  balance value at this node must be adjusted, possibly
  327.    *                  by rotating the tree at this node.
  328.    *          LorR -  Indicates the TALLER subtree.
  329.    *
  330.    *  Output: A pointer to the (possibly new) root node of the subtree.
  331.    *
  332.    *  Notes:  This function may be called after a node has been added *or*
  333.    *          deleted, so LorR indicates the TALLER subtree.
  334.    * ------------------------------------------------------------------------ **
  335.    */
  336.   {
  337.   if( p->balance != LorR )
  338.     p->balance += ubi_trNormalize(LorR);
  339.   else
  340.     {
  341.     char tallerbal;  /* Balance value of the root of the taller subtree of p. */
  342.  
  343.     tallerbal = p->Link[(int)LorR]->balance;
  344.     if( ( ubi_trEQUAL == tallerbal ) || ( p->balance == tallerbal ) )
  345.       p = ( (ubi_trLEFT==LorR) ? R1(p) : L1(p) );   /* single rotation */
  346.     else
  347.       p = ( (ubi_trLEFT==LorR) ? R2(p) : L2(p) );   /* double rotation */
  348.     }
  349.   return( p );
  350.   } /* Adjust */
  351.  
  352. static ubi_avlNodePtr Rebalance( ubi_avlNodePtr Root,
  353.                                  ubi_avlNodePtr subtree,
  354.                                  char           LorR )
  355.   /* ------------------------------------------------------------------------ **
  356.    * Rebalance the tree following an insertion.
  357.    *
  358.    *  Input:  Root    - A pointer to the root node of the whole tree.
  359.    *          subtree - A pointer to the node that has just gained a new
  360.    *                    child.
  361.    *          LorR    - Gender of the child that has just been gained.
  362.    *
  363.    *  Output: A pointer to the (possibly new) root of the AVL tree.
  364.    *          Rebalancing the tree moves nodes around a bit, so the node
  365.    *          that *was* the root, may not be the root when we're finished.
  366.    *
  367.    *  Notes:  Rebalance() must walk up the tree from where we are (which is
  368.    *          where the latest change occurred), rebalancing the subtrees
  369.    *          along the way.  The rebalancing operation can stop if the
  370.    *          change at the current subtree root won't affect the rest of
  371.    *          the tree.  In the case of an addition, if a subtree root's
  372.    *          balance becomes EQUAL, then we know that the height of that
  373.    *          subtree has not changed, so we can exit.
  374.    * ------------------------------------------------------------------------ **
  375.    */
  376.   {
  377.   while( subtree )
  378.     {
  379.     subtree = Adjust( subtree, LorR );
  380.     if( ubi_trPARENT == subtree->gender )
  381.       return( subtree );
  382.     if( ubi_trEQUAL == subtree->balance )
  383.       return( Root );
  384.     LorR = subtree->gender;
  385.     subtree = subtree->Link[ubi_trPARENT];
  386.     }
  387.   return( Root );
  388.   } /* Rebalance */
  389.  
  390. static ubi_avlNodePtr Debalance( ubi_avlNodePtr Root,
  391.                                  ubi_avlNodePtr subtree,
  392.                                  char           LorR )
  393.   /* ------------------------------------------------------------------------ **
  394.    * Rebalance the tree following a deletion.
  395.    *
  396.    *  Input:  Root    - A pointer to the root node of the whole tree.
  397.    *          subtree - A pointer to the node who's child has just "left the
  398.    *                    nest".
  399.    *          LorR    - Gender of the child that left.
  400.    *
  401.    *  Output: A pointer to the (possibly new) root of the AVL tree.
  402.    *          Rebalancing the tree moves nodes around a bit, so the node
  403.    *          that *was* the root, may not be the root when we're finished.
  404.    *
  405.    *  Notes:  Debalance() is subtly different from Rebalance() (above) in
  406.    *          two respects.
  407.    *            * When it calls Adjust(), it passes the *opposite* of LorR.
  408.    *              This is because LorR, as passed into Debalance() indicates
  409.    *              the shorter subtree.  As we move up the tree, LorR is
  410.    *              assigned the gender of the node that we are leaving (i.e.,
  411.    *              the subtree that we just rebalanced).
  412.    *            * We know that a subtree has not changed height if the
  413.    *              balance becomes LEFT or RIGHT.  This is the *opposite* of
  414.    *              what happens in Rebalance().
  415.    * ------------------------------------------------------------------------ **
  416.    */
  417.   {
  418.   while( subtree )
  419.     {
  420.     subtree = Adjust( subtree, ubi_trRevWay(LorR) );
  421.     if( ubi_trPARENT == subtree->gender )
  422.       return( subtree );
  423.     if( ubi_trEQUAL != subtree->balance )
  424.       return( Root );
  425.     LorR = subtree->gender;
  426.     subtree = subtree->Link[ubi_trPARENT];
  427.     }
  428.   return( Root );
  429.   } /* Debalance */
  430.  
  431.  
  432. /* -------------------------------------------------------------------------- **
  433.  * The next two functions are used for general tree manipulation.  They are
  434.  * each slightly different from their ubi_BinTree counterparts.
  435.  * -------------------------------------------------------------------------- **
  436.  */
  437.  
  438. static void ReplaceNode( ubi_avlNodePtr *parent,
  439.                          ubi_avlNodePtr  oldnode,
  440.                          ubi_avlNodePtr  newnode )
  441.   /* ------------------------------------------------------------------------ **
  442.    * Remove node oldnode from the tree, replacing it with node newnode.
  443.    *
  444.    * Input:
  445.    *  parent   - A pointer to he parent pointer of the node to be
  446.    *             replaced.  <parent> may point to the Link[] field of
  447.    *             a parent node, or it may indicate the root pointer at
  448.    *             the top of the tree.
  449.    *  oldnode  - A pointer to the node that is to be replaced.
  450.    *  newnode  - A pointer to the node that is to be installed in the
  451.    *             place of <*oldnode>.
  452.    *
  453.    * Notes:    Don't forget to free oldnode.
  454.    *           The only difference between this function and the ubi_bt
  455.    *           version is that the node size is sizeof( ubi_avlNode ), not
  456.    *           sizeof( ubi_btNode ).
  457.    * ------------------------------------------------------------------------ **
  458.    */
  459.   {
  460.   register int i;
  461.   register int avlNodeSize = sizeof( ubi_avlNode );
  462.  
  463.   for( i = 0; i < avlNodeSize; i++ )
  464.     ((unsigned char *)newnode)[i] = ((unsigned char *)oldnode)[i];
  465.   (*parent) = newnode;
  466.  
  467.   if(oldnode->Link[ubi_trLEFT ] )
  468.     (oldnode->Link[ubi_trLEFT ])->Link[ubi_trPARENT] = newnode;
  469.   if(oldnode->Link[ubi_trRIGHT] )
  470.     (oldnode->Link[ubi_trRIGHT])->Link[ubi_trPARENT] = newnode;
  471.   } /* ReplaceNode */
  472.  
  473. static void SwapNodes( ubi_btRootPtr  RootPtr,
  474.                        ubi_avlNodePtr Node1,
  475.                        ubi_avlNodePtr Node2 )
  476.   /* ------------------------------------------------------------------------ **
  477.    * This function swaps two nodes in the tree.  Node1 will take the place of
  478.    * Node2, and Node2 will fill in the space left vacant by Node 1.
  479.    *
  480.    * Input:
  481.    *  RootPtr  - pointer to the tree header structure for this tree.
  482.    *  Node1    - \
  483.    *              > These are the two nodes which are to be swapped.
  484.    *  Node2    - /
  485.    *
  486.    * Notes:
  487.    *  This function does a three step swap, using a dummy node as a place
  488.    *  holder.  This function is used by ubi_avlRemove().
  489.    *  The only difference between this function and its ubi_bt counterpart
  490.    *  is that the nodes are ubi_avlNodes, not ubi_btNodes.
  491.    * ------------------------------------------------------------------------ **
  492.    */
  493.   {
  494.   ubi_avlNodePtr *Parent;
  495.   ubi_avlNode     dummy;
  496.   ubi_avlNodePtr  dummy_p = &dummy;
  497.  
  498.   if( Node1->Link[ubi_trPARENT] )
  499.     Parent = &((Node1->Link[ubi_trPARENT])->Link[(int)(Node1->gender)]);
  500.   else
  501.     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
  502.   ReplaceNode( Parent, Node1, dummy_p );
  503.  
  504.   if( Node2->Link[ubi_trPARENT] )
  505.     Parent = &((Node2->Link[ubi_trPARENT])->Link[(int)(Node2->gender)]);
  506.   else
  507.     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
  508.   ReplaceNode( Parent, Node2, Node1 );
  509.  
  510.   if( dummy_p->Link[ubi_trPARENT] )
  511.     Parent = &((dummy_p->Link[ubi_trPARENT])->Link[(int)(dummy_p->gender)]);
  512.   else
  513.     Parent = (ubi_avlNodePtr *)&(RootPtr->root);
  514.   ReplaceNode( Parent, dummy_p, Node2 );
  515.   } /* SwapNodes */
  516.  
  517.  
  518. /* ========================================================================== **
  519.  *         Public, exported (ie. not static-ly declared) functions...
  520.  * -------------------------------------------------------------------------- **
  521.  */
  522.  
  523. ubi_avlNodePtr ubi_avlInitNode( ubi_avlNodePtr NodePtr )
  524.   /* ------------------------------------------------------------------------ **
  525.    * Initialize a tree node.
  526.    *
  527.    *  Input:   NodePtr  - pointer to a ubi_btNode structure to be
  528.    *                      initialized.
  529.    *  Output:  a pointer to the initialized ubi_avlNode structure (ie. the
  530.    *           same as the input pointer).
  531.    * ------------------------------------------------------------------------ **
  532.    */
  533.   {
  534.   (void)ubi_btInitNode( (ubi_btNodePtr)NodePtr );
  535.   NodePtr->balance = ubi_trEQUAL;
  536.   return( NodePtr );
  537.   } /* ubi_avlInitNode */
  538.  
  539. ubi_trBool ubi_avlInsert( ubi_btRootPtr   RootPtr,
  540.                           ubi_avlNodePtr  NewNode,
  541.                           ubi_btItemPtr   ItemPtr,
  542.                           ubi_avlNodePtr *OldNode )
  543.   /* ------------------------------------------------------------------------ **
  544.    * This function uses a non-recursive algorithm to add a new element to
  545.    * the tree.
  546.    *
  547.    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
  548.    *                       the root of the tree to which NewNode is to be added.
  549.    *           NewNode  -  a pointer to an ubi_avlNode structure that is NOT
  550.    *                       part of any tree.
  551.    *           ItemPtr  -  A pointer to the sort key that is stored within
  552.    *                       *NewNode.  ItemPtr MUST point to information stored
  553.    *                       in *NewNode or an EXACT DUPLICATE.  The key data
  554.    *                       indicated by ItemPtr is used to place the new node
  555.    *                       into the tree.
  556.    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
  557.    *                       the tree, a duplicate node may be found.  If
  558.    *                       duplicates are allowed, then the new node will
  559.    *                       be simply placed into the tree.  If duplicates
  560.    *                       are not allowed, however, then one of two things
  561.    *                       may happen.
  562.    *                       1) if overwritting *is not* allowed, this
  563.    *                          function will return FALSE (indicating that
  564.    *                          the new node could not be inserted), and
  565.    *                          *OldNode will point to the duplicate that is
  566.    *                          still in the tree.
  567.    *                       2) if overwritting *is* allowed, then this
  568.    *                          function will swap **OldNode for *NewNode.
  569.    *                          In this case, *OldNode will point to the node
  570.    *                          that was removed (thus allowing you to free
  571.    *                          the node).
  572.    *                          **  If you are using overwrite mode, ALWAYS  **
  573.    *                          ** check the return value of this parameter! **
  574.    *                 Note: You may pass NULL in this parameter, the
  575.    *                       function knows how to cope.  If you do this,
  576.    *                       however, there will be no way to return a
  577.    *                       pointer to an old (ie. replaced) node (which is
  578.    *                       a problem if you are using overwrite mode).
  579.    *
  580.    *  Output:  a boolean value indicating success or failure.  The function
  581.    *           will return FALSE if the node could not be added to the tree.
  582.    *           Such failure will only occur if duplicates are not allowed,
  583.    *           nodes cannot be overwritten, AND a duplicate key was found
  584.    *           within the tree.
  585.    * ------------------------------------------------------------------------ **
  586.    */
  587.   {
  588.   ubi_avlNodePtr OtherP;
  589.  
  590.   if( !(OldNode) ) OldNode = &OtherP;
  591.   if( ubi_btInsert( RootPtr,
  592.                     (ubi_btNodePtr)NewNode,
  593.                     ItemPtr,
  594.                     (ubi_btNodePtr *)OldNode ) )
  595.     {
  596.     if( (*OldNode) )
  597.       NewNode->balance = (*OldNode)->balance;
  598.     else
  599.       {
  600.       NewNode->balance = ubi_trEQUAL;
  601.       RootPtr->root = (ubi_btNodePtr)Rebalance( (ubi_avlNodePtr)RootPtr->root,
  602.                                                 NewNode->Link[ubi_trPARENT],
  603.                                                 NewNode->gender );
  604.       }
  605.     return( ubi_trTRUE );
  606.     }
  607.   return( ubi_trFALSE );      /* Failure: could not replace an existing node. */
  608.   } /* ubi_avlInsert */
  609.  
  610. ubi_avlNodePtr ubi_avlRemove( ubi_btRootPtr  RootPtr,
  611.                               ubi_avlNodePtr DeadNode )
  612.   /* ------------------------------------------------------------------------ **
  613.    * This function removes the indicated node from the tree, after which the
  614.    * tree is rebalanced.
  615.    *
  616.    *  Input:  RootPtr  -  A pointer to the header of the tree that contains
  617.    *                      the node to be removed.
  618.    *          DeadNode -  A pointer to the node that will be removed.
  619.    *
  620.    *  Output: This function returns a pointer to the node that was removed
  621.    *          from the tree (ie. the same as DeadNode).
  622.    *
  623.    *  Note:   The node MUST be in the tree indicated by RootPtr.  If not,
  624.    *          strange and evil things will happen to your trees.
  625.    * ------------------------------------------------------------------------ **
  626.    */
  627.   {
  628.   ubi_btNodePtr p,
  629.                *parentp;
  630.  
  631.   /* if the node has both left and right subtrees, then we have to swap
  632.    * it with another node.
  633.    */
  634.   if( (DeadNode->Link[ubi_trLEFT]) && (DeadNode->Link[ubi_trRIGHT]) )
  635.     SwapNodes( RootPtr, DeadNode, ubi_trPrev( DeadNode ) );
  636.  
  637.   /* The parent of the node to be deleted may be another node, or it may be
  638.    * the root of the tree.  Since we're not sure, it's best just to have
  639.    * a pointer to the parent pointer, whatever it is.
  640.    */
  641.   if( DeadNode->Link[ubi_trPARENT] )
  642.     parentp = (ubi_btNodePtr *)
  643.               &((DeadNode->Link[ubi_trPARENT])->Link[(int)(DeadNode->gender)]);
  644.   else
  645.     parentp = &( RootPtr->root );
  646.  
  647.   /* Now link the parent to the only grand-child.  Patch up the gender and
  648.    * such, and rebalance.
  649.    */
  650.   if( ubi_trEQUAL == DeadNode->balance )
  651.     (*parentp) = NULL;
  652.   else
  653.     {
  654.     p = (ubi_btNodePtr)(DeadNode->Link[(int)(DeadNode->balance)]);
  655.     p->Link[ubi_trPARENT] = (ubi_btNodePtr)DeadNode->Link[ubi_trPARENT];
  656.     p->gender  = DeadNode->gender;
  657.     (*parentp) = p;
  658.     }
  659.   RootPtr->root = (ubi_btNodePtr)Debalance( (ubi_avlNodePtr)RootPtr->root,
  660.                                             DeadNode->Link[ubi_trPARENT],
  661.                                             DeadNode->gender );
  662.  
  663.   (RootPtr->count)--;
  664.   return( DeadNode );
  665.   } /* ubi_avlRemove */
  666.  
  667. int ubi_avlModuleID( int size, char *list[] )
  668.   /* ------------------------------------------------------------------------ **
  669.    * Returns a set of strings that identify the module.
  670.    *
  671.    *  Input:  size  - The number of elements in the array <list>.
  672.    *          list  - An array of pointers of type (char *).  This array
  673.    *                  should, initially, be empty.  This function will fill
  674.    *                  in the array with pointers to strings.
  675.    *  Output: The number of elements of <list> that were used.  If this value
  676.    *          is less than <size>, the values of the remaining elements are
  677.    *          not guaranteed.
  678.    *
  679.    *  Notes:  Please keep in mind that the pointers returned indicate strings
  680.    *          stored in static memory.  Don't free() them, don't write over
  681.    *          them, etc.  Just read them.
  682.    * ------------------------------------------------------------------------ **
  683.    */
  684.   {
  685.   if( size > 0 )
  686.     {
  687.     list[0] = ModuleID;
  688.     if( size > 1 )
  689.       return( 1 + ubi_btModuleID( --size, &(list[1]) ) );
  690.     return( 1 );
  691.     }
  692.   return( 0 );
  693.   } /* ubi_avlModuleID */
  694.  
  695. /* ============================== The End ============================== */
  696.